Microprocessors may achieve efficient execution of instructions by implementing a mechanism, commonly referred to as a branch prediction mechanism. A branch prediction mechanism indicates a predicted direction (taken or not taken) for a branch instruction, allowing subsequent instruction fetching to continue along the predicted instruction stream indicated by the branch prediction. A branch instruction is an instruction which causes subsequent instructions to be fetched from one of at least two addresses a sequential address identifying an instruction stream beginning with instructions which directly follow the branch instruction; and a target address identifying an instruction stream beginning at an arbitrary location in memory. A branch instruction, referred to as an “unconditional branch instruction”, always branches to the target address, while a branch instruction, referred to as a “conditional branch instruction”, may select either the sequential or the target address based on the outcome of a prior instruction. Instructions from the predicted instruction stream may be speculatively executed prior to execution of the branch instruction, and in any case are placed into the instruction processing pipeline prior to execution of the branch instruction. If the predicted instruction stream is correct, then the number of instructions executed per clock cycle is advantageously increased. However, if the predicted instruction stream is incorrect, i.e., one or more branch instructions are predicted incorrectly, then the instructions from the incorrectly predicted instruction stream are discarded from the instruction processing pipeline and the number of instructions executed per clock cycle is decreased.
In order to be effective, the branch prediction mechanism must be highly accurate such that the predicted instruction stream is correct as often as possible. Typically, increasing the accuracy of the branch prediction mechanism is achieved by increasing the complexity of the branch prediction mechanism. Among the methods used to predict branches are local branch prediction and global branch prediction. Local branch prediction involves making a prediction based on the behavior of a particular branch the past few times it was executed. Local branch prediction is most effective for branches exhibiting a strong tendency towards a particular outcome. On the other hand, global branch prediction involves making a branch prediction based on the path of execution, i.e., the history of the last few branches to have been executed. Global branch prediction is useful when the behavior of a branch is related to the behavior of the prior executed branches.
Global branch prediction may implement a special shift-register storing a bit-vector, referred to as a “global history vector”, that represents the recent path of execution. For example, the global history vector may store n bits of data. Each bit of data may be associated with a group of instructions, e.g., eight instructions, that had been fetched such as from an instruction cache. The position of a bit in the global history vector corresponds to how recently the associated group of instructions was fetched. For example, the least significant bit in the global history vector may represent the most recent fetch and the nth most significant bit may represent n fetches ago. If the group of instructions fetched contained a branch instruction whose branch was taken, then a “1” may be indicated in the global history vector corresponding to that group of instructions. Otherwise, a “0” may be indicated in the global history vector. That is, a “0” may be indicated in the global history vector if the corresponding group of instructions did not contain a branch instruction or if the group of instructions did contain one or more conditional branch instructions and each of these branches were not taken. Upon each successive fetch of a group of instructions, the global history vector is updated by shifting in an appropriate “1” or “0” and discarding the oldest bit.
If the group of instructions fetched contains a branch instruction, then a copy of the global history vector along with other information may be stored in a queue, referred to as a “branch information queue”. The global history vector may be stored in the branch information queue in order to recover the global history vector in the event of a branch mispredict. As stated above, in the event of a branch mispredict, i.e., in the event the predicted instruction stream is incorrect, the instructions from the incorrectly prediction instruction are discarded. Further, in the event of a branch mispredict, certain registers and mechanisms within the processor, including the global history vector and the branch information queue, must be restored to the same state that existed immediately before the discarded instructions were fetched. The discarding of instructions in the event of a branch mispredict may be referred to as a “branch flush.”
In the event of a “non-branch” flush operation, the global history vector may be discarded. A non-branch flush may refer to a flush operation (discarding of all instructions between the most recently fetched instructions and some instructions fetched earlier ) not resulting from a branch misprediction, i.e., not resulting from an incorrectly predicted instruction stream. For example, a non-branch flush operation may be enacted to handle a “livelock” situation such as when a thread in a multi-thread system cannot make forward progress because of a resource being locked. In another example, a non-branch flush operation may be enacted when a system call instruction is fetched and later identified after a number of instructions had been fetched. The instructions fetched after the system call was fetched may have to be flushed.
The global history vector may be recoverable in a non-branch flush if the flush is to a fetch group (group of instructions fetched) that contains a branch instruction. The global history vector may be recoverable as a copy of the global history vector may have been stored in the branch issue queue for that branch instruction. However, the global history vector is not recoverable in a non-branch flush if the flush is to a fetch group that does not contain a branch instruction. The branch information queue may only contain a copy of the global history vector for a branch instruction and not for a non-branch instruction. Consequently, the global history vector must be reconstructed. If the global history vector is n bits long, then it will require n correctly predicted fetches to be reconstructed. If a correct prediction as to whether a conditional branch instruction should be taken or not taken depends on the global history vector, then branch mispredictions may occur until the global history vector has finished being reconstructed which may retard the process of reconstructing the global history vector. If non-branch flushes are frequent, then frequent branch mispredictions may occur thereby adversely affecting performance.
Therefore, there is a need in the art to recover a global history vector in the event of a non-branch flush to a fetch group of instructions that contains no branch instructions.